\documentclass[E:/GsjzTle/main/main.tex]{subfiles}
\begin{document}

\textbf{给定正整数 \(n\)，求 \(1\le x,y\le n\) 且 \(\gcd(x,y)\)
为素数的数对 \((x,y)\) 有多少对}

\begin{itemize}
\item
  \(
  \sum_{p \in \text { prime }} \sum_{i=1}^{n} \sum_{j=1}^{n}[\operatorname{gcd}(i, j)=p]
  \)
\item
  对 \(\gcd\) 进行套路式的变形：\(
  \sum_{p \in \text { prime }} \sum_{i=1}^{\left\lfloor\frac{n}{p}\right\rfloor} \sum_{j=1}^{\left\lfloor\frac{n}{p}\right\rfloor}[\operatorname{gcd}(i, j)=1
 ]\)
\item
  \(
  \sum_{p \in \text { prime }}\left(\sum_{i=1}^{\left\lfloor\frac{n}{p}\right\rfloor}\left(2 \sum_{j=1}^{i}[\operatorname{gcd}(i, j)=1]\right)-1\right)
  \) ，其中 \(-1\) 的原因是 \(i=j=1\) 时的答案会被重复统计
\item
  \(
  \sum_{p \in \text { prime }}\left(2 \sum_{i=1}^{\left\lfloor\frac{n}{p}\right\rfloor} \varphi(i)-1\right)
 \)
\item
  \(\sum_{p \in \text { prime }}\left(2 × sum\left[ \dfrac{n}{p}\right] -1\right)
 \)
\end{itemize}

\begin{lstlisting}
const int N = 1e7 + 10;
int n , prime[N] , minprime[N] , phi[N];
ll sum[N];
int euler(int n)
{
	int c=0,i,j;
	phi[1]=1;
	for(i=2; i<=n; i++)
	{
		if(!minprime[i])prime[++c]=i,minprime[i]=i,phi[i]=i-1;
		for(j=1; j<=c&&i*prime[j]<=n; j++)
		{
			minprime[i*prime[j]]=prime[j];
			if(i%prime[j]==0)
			{
				phi[i*prime[j]]=phi[i]*prime[j];
				break;
			}
			else phi[i*prime[j]]=phi[i]*(prime[j]-1);
		}
	}
	for(int i = 1 ; i <= n ; i ++) sum[i] = sum[i - 1] + phi[i];
	return c;
}
signed main()
{
	ll res = 0;
	cin >> n;
	int cnt = euler(n);
	for(int i = 1 ; i <= cnt ; i ++) res += 2 * sum[n / prime[i]] - 1;
	cout << res << '\n';
	return 0;
}
\end{lstlisting}

\end{document}
